Convex Optimization: Defining the Standard Form Convex Problem

A convex optimization problem in standard form is the foundation of modern mathematical programming. It is defined by a convex objective function $f_0$, convex inequality constraints $f_i$, and affine equality constraints. By defining the problem over the intersection of these domains $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, we ensure that any local optimum is a global optimum.

1. Mathematical Anatomy of the Standard Form

The problem is formally stated as:

$$\begin{aligned} &\text{minimize} && f_0(x) \\ &\text{subject to} && f_i(x) \leq 0, \quad i = 1, \dots, m \\ &&& a_i^T x = b_i, \quad i = 1, \dots, p \end{aligned}$$

The feasible set is defined as $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. A critical requirement for convexity is that equality constraints must be affine ($Ax = b$), as non-linear equalities generally yield non-convex sets.

2. The Geometric Epigraph Interpretation

The epigraph form problem allows us to interpret optimization geometrically in the 'graph space' $(x, t)$. By introducing a slack variable $t$, we minimize $t$ subject to $(x, t) \in \text{epi } f_0$. This demonstrates that the feasible set, any sublevel set, and the optimal set are inherently convex.

3. The Implicit vs. Explicit Pitfall

A common misconception is that shifting constraints into the objective (making them implicit) simplifies the problem. However, making the constraints implicit has not made the problem any easier to analyze or solve, even though the resulting problem is nominally unconstrained. This is particularly true in the Oracle model (black box), where we evaluate $f(x)$ and its derivatives at a cost without knowing the explicit structure.

4. Real-World Applications

Portfolio Theory: Minimizing risk $\text{var}(c^T x) = x^T \Sigma x$ for 4 assets (e.g., Asset 1 with 12% return/20% SD).
Engineering: Structural constraints like $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
Probability: Loss risk constraints $\Phi^{-1}(\beta) \leq 0$.

🎯 Core Principle

The optimality condition for a differentiable $f_0$ is given by $\nabla f_0(x)^T(y - x) \geq 0$ for all feasible $y$. This implies that the gradient must be a supporting hyperplane to the feasible set at the optimal point.

QUESTION 1

Why must equality constraints in a convex optimization problem be affine ($Ax = b$)?

Because non-linear equality constraints usually define non-convex sets.

To ensure the objective function remains differentiable.

Because the Oracle model cannot handle non-linear subroutines.

To allow the use of slack variables for inequality conversion.

QUESTION 2

In the Oracle model (black box), which of the following is true?

Evaluating the objective function has zero computational cost.

The explicit structure of the function is unknown, but we can evaluate $f(x)$ and its derivatives.

Implicit constraints make the problem significantly easier to solve than explicit ones.

The Hankel matrix must be diagonal for the model to converge.

QUESTION 3

What does the epigraph of a convex function $f_0$ represent in the context of optimization?

The set of all points where the gradient is zero.

The set of points lying on or above the graph of the function.

The intersection of all affine equality constraints.

A linear combination of monomials with real coefficients.

QUESTION 4

Which mathematical condition represents a spectral constraint on matrix $A$ being bounded by $s$?

$\|A\|_2 \leq s \iff A^T A \preceq s^2 I$

$Ax = b$

$\text{var}(c^T x) = x^T \Sigma x$

$\Phi^{-1}(\beta) \leq 0$

QUESTION 5

What is the result of introducing slack variables to an inequality constraint $f_i(x) \le 0$?

The problem becomes unconstrained.

It replaces the inequality with an equality constraint and a nonnegativity constraint.

It transforms a convex problem into a non-convex signomial problem.

The feasible set is projected onto the Hankel matrix.